package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type Queue struct {
	Head *QueueNode
	Tail *QueueNode
}

type QueueNode struct {
	Data *TreeNode
	Next *QueueNode
}

func NewQueueNode(data *TreeNode) *QueueNode {
	return &QueueNode{Data: data, Next: nil}
}

func InsertQueue(queue *Queue, data *TreeNode) {
	if queue.Head == nil {
		queue.Head = NewQueueNode(data)
		queue.Tail = queue.Head
	} else {
		qNode := NewQueueNode(data)
		queue.Tail.Next = qNode
		queue.Tail = qNode
	}
}

func PopQueue(queue *Queue) *TreeNode {
	if queue == nil {
		return nil
	}
	if queue.Head == nil {
		return nil
	}
	if queue.Head == queue.Tail {
		node := queue.Head
		queue.Head = nil
		queue.Tail = nil
		return node.Data
	}
	node := queue.Head
	queue.Head = queue.Head.Next
	return node.Data
}

func IsEmpty(queue *Queue) bool {
	if queue == nil {
		return true
	}
	if queue.Head == nil {
		return true
	}
	return false
}

func levelOrder(root *TreeNode) [][]int {
	result := [][]int{}
	if root == nil {
		return result
	}
	node := root
	queue := Queue{}
	InsertQueue(&queue, node)
	//l := []*TreeNode{}
	for !IsEmpty(&queue) {
		a := []int{}
		l := []*TreeNode{}
		for !IsEmpty(&queue) {
			node = PopQueue(&queue)
			a = append(a, node.Val)
			if node.Left != nil {
				l = append(l, node.Left)
			}
			if node.Right != nil {
				l = append(l, node.Right)
			}
		}
		result = append(result, a)
		for i := 0; i < len(l); i++ {
			InsertQueue(&queue, l[i])
		}
		//node = PopQueue(&queue)

	}
	return result
}

func main() {

}
